623D - Birthday - CodeForces Solution


greedy math probabilities *2700

Please click on ads to support us..

C++ Code:

#include <cstdio>
#include <queue>
#include <vector>

using fp = long double;

int main()
{
	int N;
	scanf("%d", &N);
	std::vector<fp> p(N);
	for(int i=0;i<N;++i)
	{
		int x;
		scanf("%d", &x);
		p[i] = (fp)x/100;
	}

	fp ans = (fp)N;
	std::vector<fp> pprod(N);
	std::vector<fp> gain(N);

	fp opt = 1;
	for(int i=0;i<N;++i)
	{
		opt *= 1 - (pprod[i] = (1 - p[i]));
		gain[i] = (1 - pprod[i] * (1 - p[i])) / (1 - pprod[i]);
	}

	auto cmp = [&](int a, int b) {return gain[a] < gain[b];};

	std::priority_queue<int, std::vector<int>, decltype(cmp)> q(cmp);
	for(int i=0;i<N;++i) q.push(i);

	ans += 1 - opt;
	for(int t=0;t<1000000;++t)
	{
		int v = q.top();
		q.pop();
		opt *= gain[v];
		pprod[v] *= (1 - p[v]);
		ans += 1 - opt;

		gain[v] = (1 - pprod[v] * (1 - p[v])) / (1 - pprod[v]);
		q.push(v);
	}
	printf("%.9lf\n", (double)ans);
	return 0;
}


Comments

Submit
0 Comments
More Questions

1178D - Prime Graph
1711D - Rain
534A - Exam
1472A - Cards for Friends
315A - Sereja and Bottles
1697C - awoo's Favorite Problem
165A - Supercentral Point
1493A - Anti-knapsack
1493B - Planet Lapituletti
747B - Mammoth's Genome Decoding
1591C - Minimize Distance
1182B - Plus from Picture
1674B - Dictionary
1426C - Increase and Copy
520C - DNA Alignment
767A - Snacktower
1365A - Matrix Game
714B - Filya and Homework
31A - Worms Evolution
1691A - Beat The Odds
433B - Kuriyama Mirai's Stones
892A - Greed
32A - Reconnaissance
1236D - Alice and the Doll
1207B - Square Filling
1676D - X-Sum
1679A - AvtoBus
1549A - Gregor and Cryptography
918C - The Monster
4B - Before an Exam